package dp.子数组;

/**
 * @author songZiHao
 * @version 1.0.0
 * @ClassName 最大子序和53.java
 * @Description https://leetcode-cn.com/problems/maximum-subarray/
 * @createTime 2021年11月01日 20:28:00
 *
 * 给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
 *
 * 子数组 是数组中的一个连续部分
 */
public class 最大子序和53 {
	public int maxSubArray(int[] nums) {
		int length = nums.length;

		if (length ==0) {
			return 0;
		}
		/**
		 * 没必要定义备忘录，dp[i][j] 表示
		 * int[][] dp=new int[length][length];
		 * 因为求得是最大值，可以直接用一个dp[i]表示0到i的最大值
		 */
		int[] dp=new int[length];

		/**
		 * 1. 状态初始化
		 * 		所有的最大值都为最小值
		 * 		dp[0]=nums[0]
		 */

		for (int i = 0; i < length; i++) {
			dp[i]=Integer.MIN_VALUE;
		}
		dp[0]=nums[0];


		/**
		 * 2. 状态转移方程
		 * 		当i=0 的时候，值为0
		 * 		当i>0 的时候，dp[i]=Max(dp[i-1]+nums[i],nums[i])
		 */

		int max=dp[0];
		for (int i = 1; i < length; i++) {
			dp[i]=Math.max(dp[i-1]+nums[i],nums[i]);
			max=Math.max(dp[i],max);
		}
		return max;
	}
}
